/*
给你两个二进制字符串，返回它们的和（用二进制表示）。

输入为 非空 字符串且只包含数字 1 和 0。

 

示例 1:

输入: a = "11", b = "1"
输出: "100"
示例 2:

输入: a = "1010", b = "1011"
输出: "10101"
 

提示：

每个字符串仅由字符 '0' 或 '1' 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 "0" ，就都不含前导零。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-binary
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
class Solution {
public:
    string addBinary(string a, string b) {
        int i=a.size()-1;
        int j=b.size()-1;
        int a_i=0;
        int b_j=0;
        int add=0;
        int cur=0;
        string new_str="";
        while(i>=0&&j>=0){
            a_i=(a[i]=='1'?1:0);
            b_j=(b[j]=='1'?1:0);
            if(a_i+b_j+add>1){
                cur=a_i+b_j+add-2;
                add=1;
            }else{
                cur=a_i+b_j+add;
                add=0;
            }
            new_str=(cur==1?'1':'0')+new_str;
            cout<<new_str<<" "<<cur<<" "<<add<<endl;
            i--;
            j--;
        }   
        while(i>=0){
            a_i=(a[i]=='1'?1:0);
            if(a_i+add>1){
                cur=a_i+add-2;
                add=1;
            }else{
                cur=a_i+add;
                add=0;
            }
            new_str=(cur==1?'1':'0')+new_str;
            i--;
        }
        while(j>=0){
            b_j=(b[j]=='1'?1:0);
            if(b_j+add>1){
                cur=b_j+add-2;
                add=1;
            }else{
                cur=b_j+add;
                add=0;
            }
            new_str=(cur==1?'1':'0')+new_str;
            
            j--;
        }

        if(add==1){
            new_str='1'+new_str;
        }
        return new_str;
    }
};